import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-23
 * Time: 23:08
 */

public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        int left = newInterval[0];
        int right = newInterval[1];
        int index = 0;
        int len = intervals.length;
        // 先处理没有重叠的部分
        while (index < len && left > intervals[index][1]) {
            list.add(intervals[index]);
            index++;
        }
        if (index == len) {
            // 遍历到最后都没有重叠
            list.add(newInterval);
        } else {
            // 处理重叠的部分
            // left <= intervals[index][1]
            // 起始位置取 较小值
            int begin = Math.min(left, intervals[index][0]);
            int end = right;
            while (index < len && right >= intervals[index][0]) {
                // 覆盖了整个区间
                end = Math.max(right, intervals[index][1]);
                index++;
            }
            list.add(new int[]{begin, end});
        }
        // 处理后面没有重叠的部分
        while (index < len) {
            list.add(intervals[index]);
            index++;
        }

        int row = list.size();
        int[][] ans = new int[row][2];
        for (int i = 0; i < row; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}
